package com.tcm.day06;

/**
 * 根据中序、后序遍历构建二叉树
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=problem-list-v2&envId=binary-tree
 */
public class Code06_BuildTreeFromInPost {

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if(null == inorder || null == postorder || inorder.length!=postorder.length){
            return null;
        }

        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }

    public static TreeNode buildTree(int[] inorder, int L1, int R1, int[] postorder, int L2, int R2) {
        if(L1 > R1) {
            return null;
        }

        TreeNode head = new TreeNode(postorder[R2]);
        if(L1 == R1){
            return head;
        }

        int idx = 0;
        while(inorder[idx] != postorder[R2]) {
            idx++;
        }

        //     1
        //    /
        //   2
        //    \
        //     3

        // idx = 2                      0     1               0    0
        head.left = buildTree(inorder, L1, idx-1, postorder, L2, L2+idx-1-L1);
        head.right = buildTree(inorder, idx+1, R1, postorder, L2+idx-L1, R2-1);
        // 4   4                 3    3
        return head;
    }

    public static void main(String[] args) {
        buildTree(new int[]{1,2,3,4},new int[]{3,4,2,1});
    }

}
